Năm 1518 Velázquez ra lệnh ông thực hiện chuyến hành trình khám phá và tìm hiểu bên trong Mexico để thuộc địa hóa vùng đất này. Vào phút cuối, do sự căng thẳng cũ giữa Velázquez và Cortés, Velázquez đã thay đổi ý định và rút lại mệnh lệnh của mình. Cortés đã phớt lờ những mệnh lệnh và thẳng tiến, vào tháng 2 năm 1519, mở một cuộc binh biến. Cùng với khoảng 11 tàu, 500 người, 13 ngựa và một ít pháo, ông đã đổ bộ lên bán đảo Yucata thuộc lãnh thổ Maya.[4] Ở đó, ông gặp một linh mục người Tây Ban Nha Geronimo de Aguilar, ông này đã sống sót sau một vụ đắm tàu và bị người Maya bản địa giam cầm một thời gian trước khi thoát ra được.[4] Aguilar đã học tiếng Chontal Maya trong thời gian bị giam giữ, và vì thế có thể phiên dịch cho Cortés. Vào tháng 3 năm 1519, Cortés chính thức tuyên bố vùng đất cho vua Tây Ban Nha. Ông dừng ở Trinidad để thuê thêm lính và tìm thêm ngựa. Sau đó ông đến Tabasco, ở đây ông gặp sự chống đối và đã chiến thắng trong trận chiến chống lại của người bản địa. Ông thu nhận 20 người phụ nữ da đỏ trẻ từ người bản xứ bại trận và bắt họ cải đạo sang Thiên Chúa giáo.[5] Trong số những người phụ nữ này có La Malinche, sau này là mẹ của con ông Martín. Malinche biết cả hai thứ tiếng Nahuatl và Chontal Maya, do đó đã giúp Cortés thương thảo với người Aztec qua Aguilar. Thông qua La Malinche, Cortés đã biết được từ người Tabascan về sự thịnh vượng của đế chế Aztec.

Tháng 7 năm 1519, đội quân của ông chiếm Veracruz: bằng hành động này, Cortés đã bãi bỏ quyền thống đốc của Cuba để điều hành dưới sự chỉ đạo trực tiếp của King Charles.[4]